$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \renewcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mss}{\,\mathrm{\frac{m}{s^2}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$

Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Техника два показивача

Угнежђене петље обично подразумевају постојање две бројачке променљиве од којих спољашња само увећава своју вредност током итерације, док се вредност бројачке петље у унутрашњој увећава до неке горње границе, затим се поново враћа на неку доњу границу и поново увећава и то се понавља више пута, све док спољашња бројачка променљива не достигне своју максималну вредност. Ово по правилу доводи до квадратне сложености (тј. сложености вишег степена у случају угнежђавања већег броја петљи).

Техника два показивача обухвата широку класу ефикасних алгоритама које такође карактерише постојање две или више бројачких променљивих, које се крећу кроз елементе неког низа (често сортираног). Међутим, оно што је карактеристично за њих је то што се, за разлику од унутрашњих променљивих у угнежђеним петљама, ове променљиве стално “крећу у истом смеру”, тј. вредност им се или стално повећава или стално смањује (а честа је и комбинација где се “низ обилази са два краја”, где се једна променљива стално повећава, а друга стално смањује). Техничка реализација може бити било помоћу једне петље која контролише вредности обе променљиве, било помоћу угнежђених петљи, али тако да се након завршетка тела унутрашње петље, спољашња променљива увећава до места где се унутрашња петља завршила. Пошто се свака променљива може променити највише \(n\) пута (где је \(n\) неко горње ограничење њихове вредности, обично дужина низа), број промена (па самим тим и извршавања тела петље) је највише \(2n\) и линеаран је по \(n\) тј. сложеност му је \(O(n)\).

Алгоритми засновани на техници два показивача обично могу да се изведу коришћењем одсецања примењених на угнежђене петље, па је, као и код сваке примене одсецања, потребно пажљиво образложити њихову коректност.

Техника два показивача — Problems

Обједињавање

CanSeeSolution
Tried: 639, Solved: 90%

Сортирани квадрати бројева

CanSeeSolution
Tried: 277, Solved: 73%

Заједнички елементи три уређена низа

Tried: 561, Solved: 72%

Близанци

Tried: 598, Solved: 87%

Прости чиниоци 235

CanSeeSolution
Tried: 234, Solved: 75%

Сегмент датог збира у низу природних бројева

CanSeeSolution
Tried: 205, Solved: 27%

Број сегмената малог збира

Tried: 118, Solved: 73%

Кајмак

Tried: 108, Solved: 79%

Тастатура и миш

Tried: 248, Solved: 79%

Двобојка

CanSeeSolution
Tried: 149, Solved: 91%

Тробојка

CanSeeSolution
Tried: 102, Solved: 91%

Оптимални сервис

Tried: 129, Solved: 79%

Два блиска предајника

Tried: 142, Solved: 90%

Светиљка

Tried: 86, Solved: 83%

Број парова датог збира

Tried: 403, Solved: 88%

Тројке датог збира (3sum)

Tried: 221, Solved: 88%

Разлика висина

CanSeeSolution
Tried: 159, Solved: 67%

Пуно фигурица

Tried: 282, Solved: 69%

Пар производа у ранцу

CanSeeSolution
Tried: 61, Solved: 73%

Број сегмената са различитим елементима

CanSeeSolution
Tried: 135, Solved: 84%

Конференција

Tried: 81, Solved: 70%

Најкраћа подниска која садржи све дате карактере

Tried: 175, Solved: 82%

Квадратно-троугаони бројеви

Tried: 59, Solved: 33%

Кружни пут

CanSeeSolution
Tried: 66, Solved: 81%

Двоструко сортирана претрага

CanSeeSolution
Tried: 87, Solved: 85%